import java.util.*;
public class TriangleNumber {
  public int triangleNumber(int[] nums) {
      int count = 0;
      if (nums == null || nums.length < 3) return 0;
      Arrays.sort(nums);
      for(int i=0;i<nums.length-2;i++){
        for(int j = i+1;j<nums.length-1;j++){
          int k = findMiddle(nums,j+1, nums.length - 1, nums[i] + nums[j]);
          // 从j+1到k-1的所有元素都满足条件，不需要逐一检查
          count += k - (j + 1);
          
        }
      }
      return count;
  }
  private static int findMiddle(int[] nums, int left, int right, int target) {
    while(left <= right){
      int mid = left + (right - left) / 2; // 在每次循环中重新计算mid
      if(nums[mid] < target){
        left = mid + 1;
      }else{
        right = mid - 1;
      }
    }
    return left; // left是第一个大于等于target的位置
  }

  public static void main(String[] args) { 
    int[] nums = {4,2,3,4};
    TriangleNumber tn = new TriangleNumber();
    System.out.println(tn.triangleNumber(nums));
  }
}

// 给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

 

// 示例 1:

// 输入: nums = [2,2,3,4]
// 输出: 3
// 解释:有效的组合是: 
// 2,3,4 (使用第一个 2)
// 2,3,4 (使用第二个 2)
// 2,2,3
// 示例 2:

// 输入: nums = [4,2,3,4]
// 输出: 4
 

// 提示:

// 1 <= nums.length <= 1000
// 0 <= nums[i] <= 1000

